package top.humbleyuan.dp;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:43
 * @Des 戳气球
 */
public class LeetCode_312 {
    public static void main(String[] args) {

        /**
         * 设k为i,j之间最后被扎破的气球
         * 缓存[i][j] = [i][k] + [k][j] + nums[i-1] * nums[j+1] + nums[k]
         * 三层循环：
         * 1. 从长度1 - n循环计算
         * 2. 每次从起始点开始计算长度为n的一段，[begin][begin+n]
         * 3. 设k为分割点，k从begin + 1开始到end - 1
         */
        int[] nums = {3,1,5,8};
        int n = nums.length;

        // 扩充
        nums = manage(nums);
        int[][] dp = new int[nums.length + 2][nums.length + 2];

        // 这里长度1表示一个数，2表示两个数，所以到n
        for (int len = 1; len <= n; len++) {

            // 由于扩充后整体后移一位，就从1，n-i+1,  原本是0，n-i
            for (int begin = 1; begin <= n - len + 1; begin++) {

                // 长度为len,那么index对应是begin + len - 1
                int end = begin + len - 1;
                //
                for (int k = begin; k <= end; k++) {
                    dp[begin][end] = Math.max(dp[begin][k-1] + dp[k+1][end] +
                            nums[begin-1] * nums[k] * nums[end+1],dp[begin][end]);
                }
            }
        }

        System.out.println(dp[1][n]);
    }

    // 扩充数组边界
    public static int[] manage(int[] nums) {
        int[] newNums = new int[nums.length + 2];
        newNums[0] = newNums[newNums.length - 1] = 1;

        System.arraycopy(nums, 0, newNums, 1, nums.length);
        return newNums;
    }
}
